package sweetsaremeat.beehive.Model;

import java.util.ArrayList;
import java.util.List;

public class PathGenerator 
{
	private Map m_map;
	
	private int m_leaderSpawnPercent = 20;
	private int m_connectPathPercent = 50; //should NEVER be 0
	private int m_minBaseSolutions = 2; //preferably > 1
	
	//this arrayList contains all leader nodes of a path
	public List<Node> m_leaders = new ArrayList<Node>();
	public List<Node> m_forks = new ArrayList<Node>(); //should remove all visible nodes from this (after GenerateBasePath)
	
	public PathGenerator(Map a_map)
	{
		m_map = a_map;
	}
	
	public void GenerateBasePath()
	{		
		if(m_map.m_startNode == null)
		{
			throw new RuntimeException("LogicGenerator.GenerateBasePath ERROR: The start node is NULL");
		}
		
		//add the first leaders
		for(int i=0; i < m_minBaseSolutions; i++)
		{
			m_leaders.add(m_map.m_startNode);
		}
		
		//initialize necessary variables
		int i, n;
		Node f_currentNode;
		int f_direction;
		int f_sides = Node.Side.values().length; //this is for optimization
		boolean f_edgeFound;
		List<Node> f_path = new ArrayList<Node>(); //this is only used when we need more solutions
		int f_backwardDir; //this is also only used when we need more solutions (to not go backwards)
		boolean f_goodFork; //this is only used when searching for a good new leader node and none was found
		
		//loop until we have at least 2 solutions
		while(true)
		{
			//loop through all leaders
			for(i=0; i < m_leaders.size(); i++)
			{
				//set current leader
				f_currentNode = m_leaders.get(i);
				
				//loop the following until we find the edge of the map
				while(true)
				{
					
					
					f_edgeFound = false;
					//check if there is a null neighbor (if we found the edge of the map)
					//TODO optimization
					//you only need to go through 3 sides, the direction where we are going and left & right of that side
					//then we will need to know which leaders are at the edge of the map, so that we can skip them
					for(n=0; n < f_sides; n++)
					{
						if(f_currentNode.m_neighbors[n] == null)
						{
							f_edgeFound = true;
							break;
						}
					}
					
					//if we found the edge of the map
					if(f_edgeFound)
					{
						break; //next leader
					}
					
					//TODO Optimization!
					//use a while loop for this part (to not check if we are at a edge node every time)
					//random direction
					f_direction = m_map.m_random.nextInt(f_sides);
					
					//see if we may continue in this direction (no other path in the way)
					if(f_currentNode.m_neighbors[f_direction].m_isPath == false)
					{
						/*
						//random if we should spawn a new leader here (the neighbor)
						//NOTE: 101 because it's half-open range
						if(m_leaderSpawnPercent != 0 && m_map.m_random.nextInt(101) <= m_leaderSpawnPercent)
						{
							//add the neighbor to the leader list
							m_leaders.add(f_currentNode.m_neighbors[f_direction]);
							
							//add the neighbor to the fork list (because it is a fork)
							m_forks.add(f_currentNode.m_neighbors[f_direction]);
						}*/
						
						//random if we should spawn a new leader here (the neighbor)
						//NOTE: 101 because it's half-open range
						if(m_leaderSpawnPercent != 0 && m_map.m_random.nextInt(101) <= m_leaderSpawnPercent)
						{
							//add the neighbor to the leader list
							m_leaders.add(f_currentNode.m_neighbors[f_direction]);
							
							//add the neighbor to the fork list (because it is a fork)
							m_forks.add(f_currentNode.m_neighbors[f_direction]);
						}
						
						//connect the path between the current node and the neighbor
						f_currentNode.ConnectPath(f_direction);
						
						//replace the current node in the leader list with the neighbor
						m_leaders.set(i, f_currentNode.m_neighbors[f_direction]);
						//set the current node to the neighbor
						f_currentNode = f_currentNode.m_neighbors[f_direction];
						
						/*
						//connect the path between the current node and the neighbor
						f_currentNode.ConnectPath(f_direction);
						
						//replace the current node in the leader list with the neighbor
						m_leaders.set(i, f_currentNode.m_neighbors[f_direction]);
						
						
						//random if we should spawn a new leader here (the current node)
						//NOTE: 101 because it's half-open range
						if(m_leaderSpawnPercent != 0 && m_map.m_random.nextInt(101) <= m_leaderSpawnPercent)
						{
							//check if this spot is OK
							for(n=0; n < f_currentNode.m_neighbors.length; n++)
							{
								//if it has a unconnected side
								if(f_currentNode.m_connectedTo[n] == false)
								{
									//add the current node to the leader list
									m_leaders.add(f_currentNode);
									
									//add the current node to the fork list (because it is a fork)
									m_forks.add(f_currentNode);
									
									break; //to not add any more leaders here (for now)
								}
							}
						}
						
						
						//set the current node to the neighbor
						f_currentNode = f_currentNode.m_neighbors[f_direction];*/
					}
					else
					{
						//check if we are already connected to this neighbor
						//NOTE: to prevent going backwards (it might be where we came from)
						if(f_currentNode.m_connectedTo[f_direction])
						{
							continue; //random another direction
						}
						
						//random if we should connect to this neighbor
						//NOTE: 101 because it's half-open range
						if(m_connectPathPercent != 0 && m_map.m_random.nextInt(101) <= m_connectPathPercent)
						{
							//connect the path between the current node and the neighbor
							f_currentNode.ConnectPath(f_direction);
							
							//add the neighbor to the fork list (because it is a fork)
							m_forks.add(f_currentNode.m_neighbors[f_direction]);
							
							//remove the current node from the leader array
							m_leaders.remove(i);
							i--;
							break; //next leader
						}
					}
				}
			}
			
			//if we have more than the minimum amount of solutions
			if(m_leaders.size() >= m_minBaseSolutions)
			{
				break; //we are done
			}
			else
			{
				
				
				//find a good spot for a new leader (and make it a new leader)
				
				//loop until we added a new leader
				while(true)
				{
					//pick a fork by random
					f_currentNode = m_forks.get(m_map.m_random.nextInt(m_forks.size()));
					f_backwardDir = -1; //initialize the backward direction to an impossible direction
					f_path.clear();
					
					//loop until we have a path between 2 forks or 1 fork and a leader (edge node)
					while(true)
					{
						//random direction
						f_direction = m_map.m_random.nextInt(f_sides);
						
						//choose a path direction that already exists
						if(f_currentNode.m_connectedTo[f_direction] && f_direction != f_backwardDir)
						{
							//go down the path
							f_currentNode = f_currentNode.m_neighbors[f_direction];
							
							//go through each side
							n = 0; //this is the counter of connected paths
							f_edgeFound = false;
							for(i=0; i < f_sides; i++)
							{
								//check if we found a path
								if(f_currentNode.m_connectedTo[i])
								{
									n++; //path found
								}
								
								if(f_currentNode.m_neighbors[i] == null)
								{
									f_edgeFound = true;
								}
							}
							
							//check if we are at a fork (a fork has more than 2 connected paths)
							//OR at a leader (leaders are at the edges of the map)
							if(n > 2 || f_edgeFound)
							{
								break; //end of path reached
							}
							
							//save the node to the path
							f_path.add(f_currentNode);
							
							//set the new backward direction
							f_backwardDir = Node.GetOppositeSide(f_direction);
						}
					}
					
					//check if we have a path (there might have been 2 forks next to each other)
					if(f_path.size() > 0)
					{
						//random one of the nodes in the path to be the new leader!
						f_currentNode = f_path.get(m_map.m_random.nextInt(f_path.size()));
						
						//add the leader
						m_leaders.add(f_currentNode);
						
						//add it to forks (because it is one)
						m_forks.add(f_currentNode);
						
						break; //a new leader has been selected
					}
					else
					{
						//now that we have no path
						
						//check if it was an edge node that stopped the path
						if(f_edgeFound)
						{
							//we don't want to make an edge node a new leader (since it's already a leader)
							//otherwise it might result in a incorrect amount of solutions
							continue; //random a new fork
						}
						
						//we should check if we can make the fork node a leader
						//NOTE: this is to prevent infinitive loop for the scenario when all the outer nodes are forks 
						
						f_goodFork = false;
						//check if it has at least 1 side that isn't connected
						for(i=0; i < f_sides; i++)
						{
							if(f_currentNode.m_connectedTo[i] == false)
							{
								f_goodFork = true;
							}
						}
						
						//if the fork has a unconnected side
						if(f_goodFork)
						{
							//make the fork a leader
							//NOTE: we don't have to add this fork to the forks (because it should already be there)
							m_leaders.add(f_currentNode);
							
							break; //a new leader has been selected
						}
					}
				}
			}
		}
	}
	
	
	
	public void IncreaseInvisiblePath()
	{
		//initialize necessary variables
		int i, n;
		Node f_currentNode;
		int f_direction;
		int f_sides = Node.Side.values().length; //this is for optimization
		boolean f_edgeFound = false;
		List<Node> f_path = new ArrayList<Node>(); //this is only used when we need more solutions
		int f_backwardDir; //this is also only used when we need more solutions (to not go backwards)
		boolean f_goodFork; //this is only used when searching for a good new leader node and none was found
		
		//reset forks
		m_forks.clear(); //to only use the forks we create now
		
		//set the minimum amount of solutions to the 
		int f_minBaseSolutions = m_leaders.size();
		
		//check for bad input (if the leaders are not invisible)
		for(i=0; i < m_leaders.size(); i++)
		{
			if(m_leaders.get(i).m_visible)
			{
				throw new RuntimeException("A leader is not invisible");
			}
		}
		
		
		//loop until we have enough solutions
		while(true)
		{
			//loop through all leaders
			for(i=0; i < m_leaders.size(); i++)
			{
				//set current leader
				f_currentNode = m_leaders.get(i);
				
				//loop the following until we find the edge of the map
				while(true)
				{
					f_edgeFound = false;
					//check if there is a null neighbor (if we found the edge of the map)
					//TODO optimization
					//you only need to go through 3 sides, the direction where we are going and left & right of that side
					//then we will need to know which leaders are at the edge of the map, so that we can skip them
					for(n=0; n < f_sides; n++)
					{
						if(f_currentNode.m_neighbors[n] == null)
						{
							f_edgeFound = true;
							break;
						}
					}
					
					//if we found the edge of the map
					if(f_edgeFound)
					{
						break; //next leader
					}
					
					//TODO Optimization!
					//use a while loop for this part (to not check if we are at a edge node every time)
					//random direction
					f_direction = m_map.m_random.nextInt(f_sides);
					
					//check if the node in this direction is visible
					if(f_currentNode.m_neighbors[f_direction].m_visible)
					{
						//we are not allowed on the visible nodes, so we random a new direction
						continue;
					}
					
					//see if we may continue in this direction (no other path in the way)
					if(f_currentNode.m_neighbors[f_direction].m_isPath == false)
					{
						//connect the path between the current node and the neighbor
						f_currentNode.ConnectPath(f_direction);
						
						//replace the current node in the leader list with the neighbor
						m_leaders.set(i, f_currentNode.m_neighbors[f_direction]);
						
						
						//random if we should spawn a new leader here (the neighbor)
						//NOTE: 101 because it's half-open range
						if(m_leaderSpawnPercent != 0 && m_map.m_random.nextInt(101) <= m_leaderSpawnPercent)
						{
							//check if this spot is OK
							if(IsGoodInvisibleNode(f_currentNode))
							{
								//add the current node to the leader list
								m_leaders.add(f_currentNode);
								
								//add the current node to the fork list (because it is a fork)
								m_forks.add(f_currentNode);
							}
						}
						
						
						//set the current node to the neighbor
						f_currentNode = f_currentNode.m_neighbors[f_direction];
					}
					else
					{
						//check if we are already connected to this neighbor
						//NOTE: to prevent going backwards (it might be where we came from)
						if(f_currentNode.m_connectedTo[f_direction])
						{
							//check if this node is a dead end
							if(IsGoodInvisibleNode(f_currentNode) == false)
							{
								//it was a dead end, so now we have to burn down the whole thing
								BurnInvisiblePathDown(f_currentNode);
								
								//start over from the first leader
								i = -1;
								//reset the minimal amount of solutions
								//NOTE: because we removed leaders and stuff
								f_minBaseSolutions = m_leaders.size();
								break;
							}
							
							continue; //random another direction
						}
						
						//random if we should connect to this neighbor
						//NOTE: 101 because it's half-open range
						if(m_connectPathPercent != 0 && m_map.m_random.nextInt(101) <= m_connectPathPercent)
						{
							//connect the path between the current node and the neighbor
							f_currentNode.ConnectPath(f_direction);
							
							//add the neighbor to the fork list (because it is a fork)
							m_forks.add(f_currentNode.m_neighbors[f_direction]);
							
							//remove the current node from the leader array
							m_leaders.remove(i);
							i--;
							break; //next leader
						}
					}
				}
			}
			
			//if we have more than the minimum amount of solutions
			if(m_leaders.size() >= f_minBaseSolutions)
			{
				break; //we are done
			}
			else
			{
				
				
				//find a good spot for a new leader (and make it a new leader)
				//NOTE: since this function is only supposed to be in the invisible nodes we
				//		we will have to act accordingly!
				
				//loop until we added a new leader
				while(true)
				{
					//pick a fork by random
					f_currentNode = m_forks.get(m_map.m_random.nextInt(m_forks.size()));
					f_backwardDir = -1; //initialize the backward direction to an impossible direction
					f_path.clear();
					
					//loop until we have a path between 2 forks or 1 fork and a leader (edge node)
					while(true)
					{
						//random direction
						f_direction = m_map.m_random.nextInt(f_sides);
						
						//choose a path direction that already exists
						if(f_currentNode.m_connectedTo[f_direction] && f_direction != f_backwardDir)
						{
							//go down the path
							f_currentNode = f_currentNode.m_neighbors[f_direction];
							
							//go through each side
							n = 0; //this is the counter of connected paths
							f_edgeFound = false;
							for(i=0; i < f_sides; i++)
							{
								//check if we found a path
								if(f_currentNode.m_connectedTo[i])
								{
									n++; //path found
								}
								
								if(f_currentNode.m_neighbors[i] == null)
								{
									f_edgeFound = true;
								}
							}
							
							//check if we are at a fork (a fork has more than 2 connected paths)
							//OR at a leader (leaders are at the edges of the map)
							//OR we have reached a visible node
							if(n > 2 || f_edgeFound || f_currentNode.m_visible)
							{
								break; //end of path reached
							}
							
							//save the node to the path
							f_path.add(f_currentNode);
							
							//set the new backward direction
							f_backwardDir = Node.GetOppositeSide(f_direction);
						}
					}
					
					//check if we have a path (there might have been 2 forks next to each other)
					if(f_path.size() > 0)
					{
						//random one of the nodes in the path to be the new leader!
						f_currentNode = f_path.get(m_map.m_random.nextInt(f_path.size()));
						
						//add the leader
						m_leaders.add(f_currentNode);
						
						//add it to forks (because it is one)
						m_forks.add(f_currentNode);
						
						break; //a new leader has been selected
					}
					else
					{
						//now that we have no path
						
						//check if it was an edge node that stopped the path
						if(f_edgeFound || f_currentNode.m_visible)
						{
							//we don't want to make an edge node a new leader (since it's already a leader)
							//otherwise it might result in a incorrect amount of solutions
							continue; //random a new fork
						}
						
						
						//we should check if we can make the fork node a leader
						//NOTE: this is to prevent infinitive loop for the scenario when all the outer nodes are forks 
						/*
						f_goodFork = false;
						//check if it has at least 1 side that isn't connected
						//AND that it's node is invisible
						for(i=0; i < f_sides; i++)
						{
							if(f_currentNode.m_connectedTo[i] == false)
							{
								if(f_currentNode.m_neighbors[i].m_visible == false)
								{
									f_goodFork = true;
								}
							}
						}*/
						
						//if the fork has a unconnected side
						if(IsGoodInvisibleNode(f_currentNode))
						{
							//make the fork a leader
							//NOTE: we don't have to add this fork to the forks (because it should already be there)
							m_leaders.add(f_currentNode);
									
							break; //a new leader has been selected
						}
					}
				}
			}
		}
	}
	
	
	private boolean IsGoodInvisibleNode(Node a_node)
	{
		int i;
		
		//check all sides
		for(i=0; i < a_node.m_neighbors.length; i++)
		{
			//make sure there is a neighbor on this side
			if(a_node.m_neighbors[i] != null)
			{
				//if we have a unconnected side
				if(a_node.m_connectedTo[i] == false)
				{
					//if that neighbor is invisible
					if(a_node.m_neighbors[i].m_visible == false)
					{
						return true;
					}
				}
			}
		}
		
		return false;
	}
	
	
	public void BurnInvisiblePathDown(Node a_startNode)
	{
		//initialize
		int i, n;
		List<Node> f_burnList = new ArrayList<Node>();
		Node f_currentNode;
		boolean f_found;
		
		//first we add the start node to the burn list
		f_burnList.add(a_startNode);
		
		while(f_burnList.size() > 0)
		{
			//set current node to first node on the burn list
			f_currentNode = f_burnList.get(0);
			
			//spread
			for(i=0; i < f_currentNode.m_neighbors.length; i++)
			{
				//if there is a path
				if(f_currentNode.m_connectedTo[i])
				{
					//if it's invisible
					if(f_currentNode.m_neighbors[i].m_visible == false)
					{
						//make sure it's not already on the burn list
						f_found = false;
						for(n=0; n < f_burnList.size(); n++)
						{
							if(f_currentNode.m_neighbors[i] == f_burnList.get(n))
							{
								f_found = true;
								break;
							}
						}
						
						//if it was not found
						if(f_found == false)
						{
							//add it to the burn list
							f_burnList.add(f_currentNode.m_neighbors[i]);
						}
					}
					else
					{
						//make sure it's not already a leader
						f_found = false;
						for(n=0; n < m_leaders.size(); n++)
						{
							if(f_currentNode.m_neighbors[i] == m_leaders.get(n))
							{
								f_found = true;
								break;
							}
						}
						
						//if it was not found
						if(f_found == false)
						{
							//add it to the leader list
							m_leaders.add(f_currentNode.m_neighbors[i]);
						}
					}
				}
			}
			
			//remove all paths from the node
			for(n=0; n < f_currentNode.m_connectedTo.length; n++)
			{
				if(f_currentNode.m_connectedTo[n])
				{
					//disconnect this node's side
					f_currentNode.m_connectedTo[n] = false;
					
					//disconnect the other node's side
					f_currentNode.m_neighbors[n].m_connectedTo[Node.GetOppositeSide(n)] = false;
				}
			}
			//this node is no longer a path
			f_currentNode.m_isPath = false;
			
			
			//remove leaders
			for(n=0; n < m_leaders.size(); n++)
			{
				if(f_currentNode == m_leaders.get(n))
				{
					m_leaders.remove(n);
					n--;
				}
			}
			
			//remove forks
			for(n=0; n < m_forks.size(); n++)
			{
				if(f_currentNode == m_forks.get(n))
				{
					m_forks.remove(n);
					n--;
				}
			}
			
			//remove this node, since it's already been burned and to burn the next node
			f_burnList.remove(0);
		}
	}
	
}
